package tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

class LeetCode_257 {
    public static void main(String[] args) {
        TreeNodec six = new TreeNodec(6, null, null);
        TreeNodec five = new TreeNodec(5, null, null);
        TreeNodec four = new TreeNodec(4, null, null);
        TreeNodec three = new TreeNodec(3, six, null);
        TreeNodec two = new TreeNodec(2, four, five);
        TreeNodec one = new TreeNodec(1, two, three);
        LeetCode_257 leet = new LeetCode_257();
        int merge = leet.merge(one, 0, 20);
        System.out.println(merge);
    }
    public int merge(TreeNodec root,int sum,int target){
        if(root == null) return -3000;
        sum += root.val;
        if(root.left == null && root.right == null){
            if(sum == target){
                return sum;
            }else{
                return 0;
            }
        }
        return merge(root.left,sum,target) == target || merge(root.right,sum,target) == target ? target : -3000;
    }
    public int findBottomLeftValue(TreeNodec root){
        ArrayList<TreeNodec> result = new ArrayList<>();
        ArrayList<TreeNodec> floor = new ArrayList<>();
        result.add(root);
        while(!result.isEmpty()){
            floor.clear();
            int size = result.size();
            for(int i = 0;i < size;i++){
                TreeNodec cur = result.remove(0);
                floor.add(cur);
                if(cur.left != null) result.add(cur.left);
                if(cur.right != null) result.add(cur.right);
            }
        }
        return floor.get(0).val;
    }
    public List<String> binaryTreePaths(TreeNodec root) {
        ArrayList<String> result = new ArrayList<String>();
        ArrayList<Integer> records = new ArrayList<>();
        backSolu(result,records,root);
        for (int i = 0; i < result.size(); i++) {
            System.out.println(result.get(i));
        }
        return result;
    }
    public void backSolu(List<String> result,List<Integer> records,TreeNodec root){
        records.add(root.val);
        if(root.left == null && root.right == null){
            StringBuilder path = new StringBuilder();
            for (int i = 0; i < records.size(); i++) {
                if(i < records.size() - 1){
                    path.append(records.get(i) + "->");
                }else {
                    path.append(records.get(i));
                }
            }
            result.add(path.toString());
            records.remove(records.size() - 1);
            return;
        }
        if(root.left != null){
            backSolu(result,records,root.left);
        }
        if(root.right != null){
            backSolu(result,records,root.right);
        }
        records.remove(records.size() - 1);
    }
}